package com.congee02.bt.dfs.top2bottom;

import com.congee02.bt.TreeNode;

public class PseudoPalindromicPaths {

    public int pseudoPalindromicPaths (TreeNode root) {
        int[] hash = new int[10];
        return process(root, hash);
    }

    private int process(TreeNode root, int[] hash) {

        if (root == null) {
            return 0;
        }

        hash[root.val] ++;

        int ret;
        if (root.left == null && root.right == null) {
            ret = isPseudoPalindromic(hash) ? 1 : 0;
        } else {
            ret = process(root.left, hash) + process(root.right, hash);
        }

        hash[root.val] --;

        return ret;
    }

    private boolean isPseudoPalindromic(int[] hash) {

        int odds = 0;

        for (int x : hash) {
            if ((x & 1) == 1) {
                odds ++;
                if (odds > 1) {
                    return false;
                }
            }
        }

        return true;
    }


}
